package offerbook;

import java.util.HashMap;
import java.util.Map;

/**
 * Created at 2019/10/28 0028 下午 4:42
 * 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,
 * 并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
 * 如 abceafc  返回b
 * <p>
 * 方式1：从字符串开始遍历，判断后面有没有重复的。O(n²)
 * 方式2：第1遍遍历统计字符串个数 ，第二遍找出最早为1的元素。
 * 如果是用HashMap保存，那么遍历一个放入一个O(1)，总体时空复杂度都是O(N)
 * 如果是TreeMap保存，那么遍历一个放入的复杂度是logn,总体时间O(nlogN)
 *
 * 方式3：也是基于以上的思想，自己存所有的ASCII码字符
 */
public class Code35_FirstNotRepeatingChar {

    public static int firstNotRepeatingChar(String str) {
        if (str == null || str.length() == 0) {
            return -1;
        }
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < str.length(); j++) {
                if (j != i && str.charAt(i) == str.charAt(j)) {
                    count++;
                }
            }
            if (count == 0) {
                return i;
            } else {
                count = 0;
            }
        }
        return -1;
    }

    /**
     * 利用HashMap，无序或者是TreeMap有序
     * 空间是O(1),因为是常数个字母
     */
    public static int firstNotRepeatingChar1(String str) {
        if (str == null || str.length() == 0) {
            return -1;
        }
        //统计字符出现个数
//        Map<Character, Integer> map = new TreeMap<>();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            //如果是hashMap下面的复杂度都是O(1)
            //如果是TreeMap复杂度是O(logn),红黑树
            if (!map.containsKey(str.charAt(i))) {
                map.put(str.charAt(i), 1);
            } else {
                map.put(str.charAt(i), map.get(str.charAt(i)) + 1);
            }
        }
        //map.forEach((k, v) -> System.out.print(k + ":" + v + "  "));
        //找第一个字符出现为1的
        for (int i = 0; i < str.length(); i++) {
            if (map.get(str.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 自己构造一个类似hashMap
     */
    public static int firstNotRepeatingChar2(String str) {
        if (str == null || str.length() == 0) {
            return -1;
        }
        // 存储ASCII码出现的次数
        int[] count = new int[256];
        for (int i = 0; i < str.length(); i++) {
            count[str.charAt(i)] ++;
        }
        //找出第一次出现的位置
        for (int i = 0; i < str.length(); i++) {
            if(count[str.charAt(i)] == 1){
                return i;
            }

        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(firstNotRepeatingChar("google"));
        System.out.println(firstNotRepeatingChar1("google"));
        System.out.println(firstNotRepeatingChar2("google"));
    }
}
